package com.gxc.hash;

import java.util.*;

/**
 * 一贫如洗的樵夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从0-N的箱子，每个箱子上面贴有箱子中藏有金币的数量。
 *
 * 从金币数量中选出一个数字集合，并销毁贴有这些数字的每个箱子，如果能销毁一半及以上的箱子，则返回这个数字集合的最小大小
 *
 * 输入描述
 * 一个数字字串，数字之间使用逗号分隔，例如：6,6,6,6,3,3,3,1,1,5
 *
 * 字串中数字的个数为偶数，并且
 *
 * 1 ≤ 字串中数字的个数 ≤ 100000
 * 1 ≤ 每个数字 ≤ 100000
 * 输出描述
 * 这个数字集合的最小大小，例如: 2
 */
public class RobberBox {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String numString = scanner.nextLine();
        String[] split = numString.split(",");
        int half = split.length/2;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < split.length; i++) {
            map.put(split[i], map.getOrDefault(split[i], 0) + 1);
        }
        Collection<Integer> values = map.values();
        ArrayList<Integer> list = new ArrayList<>(values);
        list.sort(Collections.reverseOrder());
        int sum = 0;
        int i = 0;
        for (; i < list.size(); i++) {
            sum += list.get(i);
            if (sum > half) break;
        }
        System.out.println(i+1);
    }
}
